"""
39. 组合总和
https://leetcode.cn/problems/combination-sum/description/

给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

**candidates 中的数字可以无限制重复被选取。**

说明：

所有数字（包括 target）都是正整数。
解集不能包含重复的组合。
示例 1：

输入：candidates = [2,3,6,7], target = 7,
所求解集为： [ [7], [2,2,3] ]
示例 2：

输入：candidates = [2,3,5], target = 8,
所求解集为： [ [2,2,2,2], [2,3,3], [3,5] ]
"""

from typing import List


class Solution:
    
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        result = []
        path = []
        self.backtrack(path, candidates, 0, 0, target, result)
        return result
        

    def backtrack(self, path:List, candidates, sum, indx, target, result):
        """
        回溯优先想的是遍历树
        树的节点是？
        树的层级关系是什么，递归中的循环，是遍历树的一层
        """
        for i, num in enumerate(candidates[indx:]):
            if sum + num < target:
                path.append(num)
                self.backtrack(path, candidates, sum+num, indx+i, target, result)
                path.pop(-1)
            elif sum + num == target:
                path.append(num)
                result.append(path[:])
                path.pop(-1)
        return

if __name__ == "__main__":
    candidates = [2,3,5]
    target = 8
    s = Solution()
    ans = s.combinationSum(candidates, target)
    print(ans)
    
    # 输出: [[2,2,2,2],[2,3,3],[3,5]]
        